#pragma once

#include <iostream>
#include <string>

template<typename T>
struct Foo {
  void f();
};

#define Rank int
#define ListNodePosi(T) ListNode<T>*

template <typename T>
struct ListNode
{
  T data;
  ListNodePosi(T) pred;
  ListNodePosi(T) succ;

  ListNode() { }
  ListNode(T v, ListNodePosi(T) p = nullptr, ListNodePosi(T) s = nullptr)
    : data(v),
    pred(p),
    succ(s)
  {
  }

  ListNodePosi(T) insertAsPred(T const& e);
  ListNodePosi(T) insertAsSucc(T const& e);
};

template <typename T>
class List
{
private:
  int _size;
  ListNodePosi(T) header;
  ListNodePosi(T) tailer;

protected:
  void init();
  int clear();
  void copyNodes(ListNodePosi(T), int);
  void merge(ListNodePosi(T)&, int, List<T>&, ListNodePosi(T), int);
  void mergeSort(ListNodePosi(T)&, int);
  void selectionSort(ListNodePosi(T), int);
  void insertSort(ListNodePosi(T), int);

public:
  List();
  List(List<T> const& L);
  List(List<T> const& L, Rank r, int n);
  List(ListNodePosi(T) p, int n);
  ~List();
  Rank size() const { return _size; }
  bool empty() const { return _size == 0; }
  T& operator[](Rank r) const;
  ListNodePosi(T) first() { return header->succ; };
  ListNodePosi(T) last() { return tailer->pred; };
  bool valid(ListNodePosi(T) p) { return p && (p != tailer) && (p != header); }
  int disordered() const;
  ListNodePosi(T) find(T const& e) const;
  ListNodePosi(T) find(T const& e, int n, ListNodePosi(T) p) const;
  ListNodePosi(T) search(T const& e) const;
  ListNodePosi(T) search(T const& e, int n, ListNodePosi(T) p) const;
  ListNodePosi(T) selectMax(ListNodePosi(T) p, int n) const;
  ListNodePosi(T) selectMax();
  //
  void append(T const& e);
  ListNodePosi(T) insertAsFirst(T const& e);
  ListNodePosi(T) insertAsLast(T const& e);
  ListNodePosi(T) insertA(ListNodePosi(T) p, T const& e);
  ListNodePosi(T) insertB(ListNodePosi(T) p, T const& e);
  T remove(ListNodePosi(T) p);
  void merge(List<T>& L);
  void sort(ListNodePosi(T) p, int n);
  void sort() { sort(first(), _size); };
  //void sort(int method) { sort(first(), method); };
  int deduplicate();
  int uniquify();
  //void reverse();

  void traverse(void(*)(T&));
  template <typename VST>
  void traverse(VST&);
};

#include "list-impl.hpp"